package psn.zjk.career.interview.algorithm;

/**
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 * <p>
 * k 是一个正整数，它的值小于或等于链表的长度。
 * <p>
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * @author zhangjk
 * @Description
 * @CREATE_TIME 2021/3/24 19:46
 */
public class LCOffer25 {

    /** 不参考答案，直接写：
     * 每k次翻转一遍，end.next=翻转返回
     * */
    public ListNode reverseKGroup(ListNode head, int k) {
        int tmp = 0;
        ListNode node = head;
        ListNode[] arr = new ListNode[k];
        ListNode firstNode = head;
        ListNode lastNode = null;
        while (tmp < k && node != null) {
            arr[tmp] = node;
            node = node.next;
            tmp++;
            if (tmp == k) {
                while (tmp > 0) {
                    if (lastNode == null) {
                        firstNode = arr[--tmp];
                        lastNode = firstNode;
                    } else {
                        lastNode.next = arr[--tmp];
                        lastNode = lastNode.next;
                    }
                }
                lastNode.next = reverseKGroup(node, k);
                break;
            }

        }
        return firstNode;
    }

    //反转链表
    private ListNode reverse(ListNode head) {
        ListNode newLink = null;
        ListNode curr = head;
        //每次循环：处理当前节点，使其指向新链表，curr指针后移；
        // 未处理链表和新链表没有直接关系，但循环直到未处理链表为空
        while (curr != null) {
            //保存未处理的
            ListNode unReversed = curr.next;
            //当前节点指向新链表
            curr.next = newLink;
            //保存
            newLink = curr;
            //未处理链表作为当前节点
            curr = unReversed;
        }
        return newLink;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
//        System.out.println(new LCOffer25().reverseKGroup(listNode, 2));;
        System.out.println(new LCOffer25().reverse(listNode));;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return val + " => " + next;
        }
    }
}